/*
提交链接：https://leetcode.cn/problems/count-special-integers/submissions/572339517
2376. 统计特殊整数-困难
完成日期：2024/10/13
数位DP
*/

class Solution {
public:
    int dp(vector<int>& con, int len, int n, long offset, int free, int num)
    {
        if(len == 0)
        {
            return num == 1 ? 1 : 0;
        }
        int ans = 0;
        if(free)
        {
            if(num)
            {
                for(int i = 0; i < con.size(); i++)
                {
                    if(con[i])
                    {
                        con[i] = 0;
                        ans += dp(con, len - 1, n, offset / 10, 1, 1);
                        con[i] = 1;
                    }
                }
            }
            else
            {
                ans += dp(con, len - 1, n, offset / 10, 1, 0);
                for(int i = 1; i < con.size(); i++)
                {
                    if(con[i])
                    {
                        con[i] = 0;
                        ans += dp(con, len - 1, n, offset / 10, 1, 1);
                        con[i] = 1;
                    }
                }
            }
        }
        else
        {
            if(n / offset < 10)
            {
                ans += dp(con, len - 1, n, offset / 10, 1, 0);
            }
            int a = 1;
            if(num)
            {
                a = 0;
            }
            for(int i = a; i < con.size(); i++)
            {
                if(con[i] > 0 && i < n / offset % 10)
                {
                    con[i] = 0;
                    ans += dp(con, len - 1, n, offset / 10, 1, 1);
                    con[i] = 1;
                }
                else if(con[i] > 0 && i == n / offset % 10)
                {
                    con[i] = 0;
                    ans += dp(con, len - 1, n, offset / 10, 0, 1);
                    con[i] = 1;
                }
            }
        }
        return ans;
    }
    int countSpecialNumbers(int n) 
    {
        int num = n;
        int len = 0;
        long offset = 1;
        while(num)
        {
            num /= 10;
            len++;
            offset *= 10;
        }
        offset /= 10;
        vector<int> con(10, 1);
        return dp(con, len, n, offset, 0, 0);
        
    }
};